package com.yulongtian.oneProblemEveryDay.month202212;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * https://leetcode.cn/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/
 *
 * @author yulongTian
 * @create 2022-12-01 16:44
 */
public class Test01 {
    public static void main(String[] args) {
        int[][] points = {{1, 1}, {6, 2}, {1, 5}, {3, 1}};
        System.out.println(nearestValidPoint(5, 1, points));
    }

//    public static int nearestValidPoint(int x, int y, int[][] points) {
//
//        //记录当前最小的曼哈顿距离
//        int manHaDunDist = Integer.MAX_VALUE;
//
//        //哈希表 key:曼哈顿距离，value:List<int[2]>点坐标
//        HashMap<Integer, List<int[]>> myMap = new HashMap<>();
//
//        //是否有有效点
//        boolean flag = false;
//
//        for (int i=0;i<points.length;i++) {
//            int[] point = points[i];
//            int p_x = point[0];
//            int p_y = point[1];
//
//            if (p_x == x || p_y == y) {
//                if (!flag) {
//                    flag = true;
//                }
//
//                //计算曼哈顿距离
//                int tempDist = Math.abs(p_x - x) + Math.abs(p_y - y);
//
//                //如果比当前的最小曼哈顿距离（manHaDunDist）小就加入 否则不加入
//                if (tempDist < manHaDunDist) {
//
//                    //如果哈希表不为空且包含manHaDunDist就删除之前大的key
//                    if (!myMap.isEmpty() && myMap.containsKey(manHaDunDist)) {
//                        myMap.remove(manHaDunDist);
//                    }
//
//                    //如果包含tempDist
//                    if(myMap.containsKey(tempDist)){
//                        List<int[]> ints = myMap.get(tempDist);
//                        ints.add(new int[]{p_x, p_y,i});
//                        myMap.put(tempDist, ints);
//                    }else{
//                        int[] temp = {p_x, p_y,i};
//                        List<int[]> tempList = new ArrayList<>();
//                        tempList.add(temp);
//                        myMap.put(tempDist, tempList);
//                    }
//
//
//                    manHaDunDist = tempDist;
//                    continue;
//                }
//
//                if (manHaDunDist == tempDist) {
//                    List<int[]> ints = myMap.get(tempDist);
//                    ints.add(new int[]{p_x, p_y,i});
//                    myMap.put(tempDist, ints);
//                }
//            }
//
//
//        }
//        //有有效点
//        if (flag) {
//            List<int[]> ints = myMap.get(manHaDunDist);
//            int min_x = Integer.MAX_VALUE;
//            int min_y = Integer.MIN_VALUE;
//            int res = 0;
//            for (int i = 0; i < ints.size(); i++) {
//                int[] temp = ints.get(i);
//
//                if (temp[0] < min_x) {
//                    min_x = temp[0];
//                    min_y = temp[1];
//                    res = temp[2];
//                    continue;
//                }
//                if (temp[0] == min_x) {
//                    if (temp[1] < min_y) {
//                        min_y = temp[1];
//                        res = temp[2];
//                    }
//                }
//
//            }
//
//
//            return res;
//
//        }
//
//
//        return -1;
//    }

    public static int nearestValidPoint(int x, int y, int[][] points) {


        //哈希表 key:曼哈顿距离，value:List<int[2]>点坐标
        HashMap<Integer, List<int[]>> myMap = new HashMap<>();

        //之前的曼哈顿距离最小的有效点 且字典序最小
        int pre_min_M_x = Integer.MAX_VALUE;
        int pre_min_M_y = Integer.MAX_VALUE;
        int pre_min_M = Integer.MAX_VALUE;

        int res = 0;

        for (int i = 0; i < points.length; i++) {
            int[] point = points[i];
            //当前遍历的点
            int cur_x = point[0];
            int cur_y = point[1];

            //有 有效点
            if (cur_x == x || cur_y == y) {

                //计算当前点的曼哈顿距离
                int tempDist = Math.abs(cur_x - x) + Math.abs(cur_y - y);

                if (tempDist < pre_min_M) {
                    pre_min_M_x = cur_x;
                    pre_min_M_y = cur_y;
                    pre_min_M = tempDist;
                    res = i;
                    continue;
                }

                if (tempDist == pre_min_M) {
                    if (cur_x < pre_min_M_x) {

                        if (pre_min_M_x == x) {
                            continue;
                        }

                        pre_min_M_x = cur_x;
                        pre_min_M_y = cur_y;
                        res = i;
                        continue;
                    }
                    if (cur_x == pre_min_M_x) {

                        if (pre_min_M_x == x) {
                            continue;
                        }

                        if (cur_y < pre_min_M_y) {
                            pre_min_M_y = cur_y;
                            res = i;
                        }
                    }
                }


            }
        }

        if (pre_min_M == Integer.MAX_VALUE) {
            return -1;
        }
        System.out.println(points[6310][0] + "," + points[6310][1]);
        System.out.println(points[1048][0] + "," + points[1048][1]);

        return res;

    }

}
